package br.edu.ufcg.mdaveritas.bfs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

import br.edu.ufcg.mdaveritas.net.Net;
import br.edu.ufcg.mdaveritas.net.NetObject;
import br.edu.ufcg.mdaveritas.net.Node;


public class BFS {

	private Queue<Node> queue;
	private Map<Node, Boolean> nodes;
	private Queue<Node> nodesList;
	
	public BFS(Net net) {
		queue = new LinkedList<Node>();
		nodes = new HashMap<Node, Boolean>();
		nodesList = new LinkedList<Node>();
		for (Iterator<NetObject> iterator = net.getObjects().iterator(); iterator.hasNext();) {
			NetObject n = (NetObject) iterator.next();
			if (n instanceof Node) {
				nodes.put((Node) n, false);
				nodesList.add((Node) n);
			}
		}
	}
	
	public List<Node> getPreAndPosSet(Node n) {
		List<Node> pList = new ArrayList<Node>();
		pList.addAll(n.getPreSet());
		pList.addAll(n.getPosSet());
		
		return pList;
	}
	
	private boolean isVisited(Node n) {
		return nodes.get(n);
	}
	
	private void setVisited(Node n) {
		nodes.put(n, true);
	}
	
	private Node getUnvisited() {
		for (Iterator<Map.Entry<Node,Boolean>> iterator = nodes.entrySet().iterator(); iterator
				.hasNext();) {
			Map.Entry<Node,Boolean> entry = (Map.Entry<Node,Boolean>) iterator.next();
			if (!entry.getValue()) {
				return entry.getKey();
			}
		}
		return null;
	}
	
	public List<Node> search() {
		int subnet = 3;
		List<Node> subnets = new ArrayList<Node>();
		while(nodes.containsValue(false)) {
			Node aNode = getUnvisited();
			setVisited(aNode);
			queue.add(aNode);
			while (!queue.isEmpty()) {
				Node u = queue.remove();
				List<Node> preAndPosSet = getPreAndPosSet(u);
				for (Node node : preAndPosSet) {
					if (!isVisited(node)) {
						setVisited(node);
						queue.add(node);
					}
				}
				setVisited(u);
			}
			System.out.println("===");
			for (Map.Entry<Node,Boolean> entry : nodes.entrySet()) {
				if (entry.getValue() && nodesList.contains(entry.getKey())) {
					System.out.println(entry.getKey().getName() + " in subnet " + subnet);
					Node n = entry.getKey();
					n.setSubnet(subnet);
					subnets.add(n);
					nodesList.remove(entry.getKey());
				}				
			}
			subnet++;
		}
		return subnets;
	}
	
//	public static void main(String[] args) {
//		Net net = new Net();
//		Node a = new Node("A");
//		Node b = new Node("B");
//		Node c = new Node("C");
//		Node d = new Node("D");
//		Node e = new Node("E");
//		Node f = new Node("F");
//		Node g = new Node("G");
//		Node h = new Node("H");
//		a.getPreSet().add(b);
//		a.getPosSet().add(c);
//		b.getPreSet().add(d);
//		b.getPosSet().add(a);
//		c.getPreSet().add(a);
//		c.getPosSet().add(d);
//		d.getPreSet().add(c);
//		d.getPosSet().add(b);
//		e.getPreSet().add(f);
//		e.getPosSet().add(g);
//		f.getPreSet().add(h);
//		f.getPosSet().add(e);
//		g.getPreSet().add(e);
//		g.getPosSet().add(h);
//		h.getPreSet().add(g);
//		h.getPosSet().add(f);
//		net.getObjects().add(a);
//		net.getObjects().add(b);
//		net.getObjects().add(c);
//		net.getObjects().add(d);
//		net.getObjects().add(e);
//		net.getObjects().add(f);
//		net.getObjects().add(g);
//		BFS bfs = new BFS(net);
//		bfs.search();
//	}
}
